import re
from typing import TYPE_CHECKING, Any, Iterator, List, Optional
from abc import ABC, abstractmethod

if TYPE_CHECKING:
    from chernc.treediff.gumtree.tree.abstract_tree import TreeMetrics


class TreeLike(ABC):
    url_pattern = re.compile(r"\d+(\.\d+)*")

    NO_LABEL = ""
    NO_POS = -1
    
    @abstractmethod
    def to_tree_string(self) -> str:
        pass

    def pre_order(self) -> Iterator["TreeLike"]:
        """
        Returns a list containing the node and its descendants, ordered using a pre-order.
        """
        from chernc.treediff.gumtree.tree.tree_utils import TreeUtils
        return iter(TreeUtils.pre_order(self))

    def post_order(self) -> Iterator["TreeLike"]:
        """
        Returns a list containing the node and its descendants, ordered using a post-order.
        """
        from chernc.treediff.gumtree.tree.tree_utils import TreeUtils
        return iter(TreeUtils.post_order(self))

    def breadth_first(self) -> Iterator["TreeLike"]:
        """
        Returns a list containing the node and its descendants, ordered using a breadth-first order.
        """
        from chernc.treediff.gumtree.tree.tree_utils import TreeUtils
        return iter(TreeUtils.breadth_first(self))

    @abstractmethod
    def add_child(self, child: "TreeLike") -> None:
        """Add the given tree as a child, at the last position and update its parent."""
        pass

    @abstractmethod
    def insert_child(self, t: "TreeLike", position: int) -> None:
        """Insert the given tree at the specified position as a child, and update its parent."""
        pass

    @abstractmethod
    def set_children(self, children: List["TreeLike"]) -> None:
        """Sets the list of children of this node."""
        pass

    @abstractmethod
    def get_children(self) -> List["TreeLike"]:
        """Returns a list of children."""
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def get_pos(self) -> int:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def set_pos(self, pos: int) -> None:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def get_length(self) -> int:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def set_length(self, length: int) -> None:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def get_type(self) -> str:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def set_type(self, t: str) -> None:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def get_label(self) -> str:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def set_label(self, label: str) -> None:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def deep_copy(self) -> "TreeLike":
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def get_metrics(self) -> "TreeMetrics":
        """Returns the metrics object computed for this node."""
        pass

    @abstractmethod
    def set_metrics(self, metrics: "TreeMetrics") -> None:
        """Sets the metrics object for this node."""
        pass

    @abstractmethod
    def get_metadata(self, key: str) -> Any:
        """Returns the metadata with the given key for this node."""
        pass

    @abstractmethod
    def set_metadata(self, key: str, value: Any) -> None:
        """Sets the metadata with the given key and value for this node."""
        pass

    @abstractmethod
    def get_parent(self) -> Optional["TreeLike"]:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def set_parent(self, parent: Optional["TreeLike"]) -> None:
        raise NotImplementedError("Subclasses should implement this method.")

    @abstractmethod
    def get_height(self) -> int:
        raise NotImplementedError("Subclasses should implement this method.")

    def is_leaf(self) -> bool:
        return len(self.get_children()) == 0

    def is_root(self) -> bool:
        return self.get_parent() is None

    def get_child_position(self, child: "TreeLike") -> int:
        return self.get_children().index(child)

    def get_child(self, position: int) -> "TreeLike":
        return self.get_children()[position]

    def get_end_pos(self) -> int:
        return self.get_pos() + self.get_length()

    def get_parents(self) -> List["TreeLike"]:
        parents = []
        par = self.get_parent()
        if par is None:
            return parents
        else:
            parents.append(par)
            parents.extend(par.get_parents())
        return parents

    def get_descendants(self) -> List["TreeLike"]:
        from chernc.treediff.gumtree.tree.tree_utils import TreeUtils

        trees = TreeUtils.pre_order(self)
        trees.pop(0)
        return trees

    def has_label(self) -> bool:
        return self.get_label() != self.NO_LABEL

    def has_same_type(self, other: "TreeLike") -> bool:
        if not isinstance(other, TreeLike):
            return False
        return self.get_type() == other.get_type()

    def has_same_type_and_label(self, t: "TreeLike") -> bool:
        return self.has_same_type(t) and self.get_label() == t.get_label()

    def is_isomorphic_to(self, other: "TreeLike") -> bool:
        # Step 1: Check if the node types and label are the same
        if not self.has_same_type_and_label(other):
            return False

        # Step 2: Check if they have the same number of children
        if len(self.get_children()) != len(other.get_children()):
            return False

        # Step 3: Recursively check if each corresponding child is isomorphic
        for child1, child2 in zip(self.get_children(), other.get_children()):
            if not child1.is_isomorphic_to(child2):
                return False

        return True

    def is_iso_structural_to(self, tree: "TreeLike") -> bool:
        if self.get_type() != tree.get_type():
            return False

        if len(self.get_children()) != len(tree.get_children()):
            return False

        for i in range(len(self.get_children())):
            is_children_structural = self.get_child(i).is_iso_structural_to(tree.get_child(i))
            if not is_children_structural:
                return False

        return True

    def get_trees_between_positions(self, position: int, end_position: int) -> List["TreeLike"]:
        """Returns trees contained within the given positions interval."""
        trees = []
        for tree in self.pre_order():
            if tree.get_pos() >= position and tree.get_end_pos() <= end_position:
                trees.append(tree)
        return trees

    def get_child_by_url(self, url: str) -> "TreeLike":
        """Returns the child node at the given URL."""
        if not TreeLike.url_pattern.match(url):
            raise ValueError(f"Wrong URL format: {url}")

        path = url.split(".")
        current = self
        for segment in path:
            next_index = int(segment)
            current = current.get_child(next_index)
        return current

    def search_subtree(self, subtree: "TreeLike") -> List["TreeLike"]:
        """Searches for subtrees matching the given subtree."""
        results = []
        for candidate in self.pre_order():
            if candidate.get_metrics().hash == subtree.get_metrics().hash and candidate.is_isomorphic_to(subtree):
                results.append(candidate)
        return results

    def position_in_parent(self) -> int:
        p = self.get_parent()
        if p is None:
            return -1
        else:
            return p.get_children().index(self)